1. Field of the Invention
The present invention is directed to computer systems; and more particularly, it is directed to rendering two-dimensional artwork using computer systems.
2. Description of the Related Art
As the power and complexity of personal computer systems increase, graphics operations and graphical data are likewise increasing in complexity. Graphical data, particularly two-dimensional graphical data, may typically be expressed in a structured format that complies with a particular specification or model for representing such data. Instead of requiring application programs to describe every page as a full-resolution pixel array, a high-level imaging model may enable applications to describe the appearance of pages containing text, graphical shapes, and sampled images in terms of abstract graphical elements rather than directly in terms of device pixels. Such specifications and models may often be implemented across multiple computing platforms to facilitate the exchange of graphical data.
One such specification, the Adobe® Portable Document Format (PDF), is the native file format of the Adobe® Acrobat® family of products. By using products that implement the PDF format, users may exchange and view electronic documents in a manner that is substantially independent of the environment in which the documents were created. PDF includes an imaging model that describes text and graphics in a device-independent and resolution-independent manner. The PDF imaging model (i.e., the Adobe® Imaging Model) includes various structures to describe complex two-dimensional graphical data including geometric models and bitmapped images.
In the PDF imaging model for two-dimensional graphics, “paint” is placed on a page in selected areas. Painted figures may be in the form of character shapes, geometric shapes, lines, or sampled images (e.g., digital representations of photographs). The content stream for a page may include operands and operators describing a sequence of objects. The types of objects may include path objects, text objects, and image objects. A path object comprises a sequence of connected and disconnected points, lines, and curves that together describe shapes and their positions. The path object may be constructed through the sequential application of path construction operators, each of which appends one or more new elements. A text object comprises one or more glyph shapes representing characters of text. The glyph shapes for the characters are described in a separate data structure called a font. An image object comprises a rectangular array of sample values, each representing a color at a particular position within the rectangle. Such objects are typically used to represent photographs.
The painting operators may use various explicit or implicit parameters. Implicit parameters may include the current color, current line width, current font, etc. Together, these implicit parameters make up the graphics state. Another implicit parameter in the graphics state may modify the results of painting graphics objects. The current clipping path outlines the area of the current page within which paint can be placed. Although painting operators may attempt to place marks anywhere on the current page, only those marks falling within the current clipping path affect the page; those falling outside it do not affect the page. Initially, the current clipping path encompasses the entire imageable area of the page. The current clipping path may temporarily be reduced to the shape defined by a path or text object, or to the intersection of multiple such shapes. Marks placed by subsequent painting operators are confined within that boundary. The optimization in which graphical data outside a clip path is discarded or modified to fit the clip path is referred to herein as “clipping.”
The optimization in which graphical data outside the current field of view (e.g., offscreen) is not drawn is referred to herein as “culling.” When the current view is scrolled, some displayed objects may be hidden while undisplayed objects may need to be drawn anew. Culling may be used in this scenario to minimize the number of redrawn objects. When scrolling, it is often possible to reuse some of the rasterization already inside the view (e.g., if the user scrolled the view by a small factor). Reusable regions may be referred to as “valid” regions, and regions that need to be re-painted (e.g., due to a scrolling operation) may be referred to as “invalid” or “dirty” regions. During a scrolling operation, the application may first move the valid pixels on screen. The application may then “invalidate” any dirty regions by deciding which part of the screen needs to be redrawn due to the scrolling.
In a prior approach, clipping is achieved by creating a stack of clipping operations that reflect nested contexts of validity of viewing. Independent “worlds” limited by a clip region may be incorporated into larger worlds, thereby creating recursive clipping regions. To render such regions, the clipping regions are walked like a tree, and every region is pushed into a clipping stack that represents the overall intersection of all the clipping regions up to this time. The clipping stack is popped when the viewer exits a clipping region, thereby restoring the previous clipping region. The current clipping region is represented typically as a set of scanlines representing the mask of the clip, and it is used to limit any marking operations to the clipping regions by making a bitwise operation with the mask. In a prior approach, the culling of objects is performed by maintaining an optimized culling table that represents the bounding boxes of the clip region.
Rendering a large and/or complex two-dimensional artwork (i.e., an artwork comprising many objects and/or especially complex objects) may require many culling and/or clipping operations. Using the prior approaches for clipping and culling, it may be necessary to perform a time-consuming set of atomic operations (e.g., culling, clipping, bitwise comparisons, marking, proceeding to the next object) for every object in the artwork, no matter how small the object.